package j20251111;

public class Solution2 {
    int m,n,k,ret;
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] vis;
    public int wardrobeFinishing(int _m, int _n, int cnt) {
        m=_m;
        n=_n;
        k=cnt;
        vis=new boolean[m][n];
        dfs(0,0);
        return ret;
    }
    public void dfs(int i,int j){
        ret++;
        vis[i][j]=true;
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&check(x,y)){
                dfs(x,y);
            }
        }
    }
    public boolean check(int i,int j){
        int tmp=0;
        while(i!=0){
            tmp+=i%10;
            i/=10;
        }
        while(j!=0){
            tmp+=j%10;
            j/=10;
        }
        return tmp<=k;
    }
}
